//Merge two sorted linked lists and return it as a sorted list. The list should 
//be made by splicing together the nodes of the first two lists. 
//
// 
// Example 1: 
//
// 
//Input: l1 = [1,2,4], l2 = [1,3,4]
//Output: [1,1,2,3,4,4]
// 
//
// Example 2: 
//
// 
//Input: l1 = [], l2 = []
//Output: []
// 
//
// Example 3: 
//
// 
//Input: l1 = [], l2 = [0]
//Output: [0]
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in both lists is in the range [0, 50]. 
// -100 <= Node.val <= 100 
// Both l1 and l2 are sorted in non-decreasing order. 
// 
// Related Topics 递归 链表 
// 👍 1700 👎 0


package leetcode.editor.cn;

//Java：Merge Two Sorted Lists
class P21MergeTwoSortedLists {
    public static void main(String[] args) {
        Solution solution = new P21MergeTwoSortedLists().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if (l1 == null) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }
            ListNode root = new ListNode(Integer.MIN_VALUE);
            ListNode node = root;
            while (l1 != null || l2 != null) {
                if (l1 != null && l2 != null && l1.val < l2.val) {
                    node.next = l1;
                    l1 = l1.next;
                    node = node.next;
                }
                if (l1 != null && l2 != null && l1.val >= l2.val) {
                    node.next = l2;
                    l2 = l2.next;
                    node = node.next;
                }
                if (l1 == null) {
                    node.next = l2;
                    break;
                }
                if (l2 == null) {
                    node.next = l1;
                    break;
                }
            }
            return root.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}